package chapter04_RecursionAndDynamic;

import chapter02_linkedList.JosephusKill;
import com.sun.xml.internal.fastinfoset.sax.SAXDocumentSerializerWithPrefixMapping;

import java.security.PublicKey;

/**
 * 描述：龙与地下城游戏
 *      给定一个二维数组map，含义是一张地图
 *      游戏的规则如下:
 *          1骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
 *          2地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽,要
 *              让骑士损失血量。如果是非负数，代表此处有血瓶，能让骑士回血。
 *          3骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。
 *              为了保证骑士能见到公主，初始血量至少是多少?根据map,返回初始血量。
 * @author hl
 * @date 2021/7/10 10:20
 */
public class minPH {
    public static void main(String[] args) {
        int[][] map = {{-2, -3, 3},{-5, -10, 1}, {0, 30, -5}};
        minPH minPH = new minPH();
        int i = minPH.minPH1(map);
        int j = minPH.minPH2(map);
        int k = minPH.minPH3(map);
        System.out.println(i);
        System.out.println(j);
        System.out.println(k);
        System.out.println((int)'a');
        System.out.println((int)'A');

    }

    /**
     * 动态规划，dp[i][j]表示来到当前位置上需要的最小的血量，
     *      如果(i, j)位置是扣血，那么来到(i, j)位置的最小血量是来到下一个位置的最小血量 - 当前位置的扣血量（负数），即
     *           dp[i][j] = dp[i+1][j] - map[i][j] 或者 dp[i][j] = dp[i][j + 1] - map[i][j]，两者取最小值
     *      如果当前位置是加血，那么在(i, j)位置的最小血量是下一个位置的最小血量 - 当前位置的加血量，即
     *          dp[i][j] = dp[i+1][j] - map[i][j] 或者 dp[i][j] = dp[i][j + 1] - map[i][j],两者取最小值
     *          需要注意的是来到每个位置的血量都不少于1，因此，如果计算的结果小于1，则让它等于1
     *
     *      考虑来到当前位置的最小血量，需要考虑去下一个位置的最小血量，因此可以从右下角开始，从右到左，从下到上进行递推
     *      dp[0][0]即是最小的初始血量
     *      右下角位置(i, j)是如果是扣血，那么来到该位置至少要1 - map[i][j]的血量，因为要保证扣完血后的血量至少为1
     *                      如果是加血，那么来到该位置至少要1 - map[i][j]的血量，如果结果为小于1，则让它为1
     * @param map
     * @return
     */
    public int minPH1(int[][] map){
        if (map == null || map.length == 0 || map[0] == null || map[0].length == 0) {
            return 1;
        }
        int row = map.length;
        int col = map[0].length;
        int[][] dp = new int[row][col];
        dp[row - 1][col - 1] = Math.max(1, 1 - map[row - 1][col - 1]);
        for (int i = row - 2; i >= 0; i--) {
            dp[i][col - 1] = Math.max(1, dp[i  + 1][col - 1] - map[i][col - 1]);
        }
        for (int j = col - 2; j >=0 ; j--) {
            dp[row - 1][j] = Math.max(1, dp[row - 1][j + 1] - map[row - 1][j]);
        }
        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                //每次选择向左或向右需要的最小的血量，同时保证当前位置的血量不小于1
                dp[i][j] = Math.max(Math.min(dp[i + 1][j] - map[i][j], dp[i][j + 1] - map[i][j]), 1);
            }
        }
        return dp[0][0];
    }

    public int minPH2(int[][] m){
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 1;
        }
        int row = m.length;
        int col = m[0].length;
        int[][] dp = new int[row--][col--];
        dp[row][col] = m[row][col] > 0 ? 1 : 1 - m[row][col];
        for (int j = col - 1; j >= 0; j--) {
            dp[row][j] = Math.max(dp[row][j + 1] - m[row][j], 1);
        }
        int right = 0;
        int down = 0;
        for (int i = row - 1; i >= 0; i--) {
            dp[i][col] = Math.max(dp[i + 1][col] - m[i][col], 1);
            for (int j = col - 1; j >= 0; j--) {
                right = Math.max(dp[i][j + 1] - m[i][j], 1);
                down = Math.max(dp[i + 1][j] - m[i][j], 1);
                dp[i][j] = Math.min(right, down);
            }
        }
        return dp[0][0];
    }

    /**
     * 空间压缩
     * @param m
     * @return
     */
    public int minPH3(int[][] m){
        if(m == null || m.length == 0 || m[0] == null || m[0].length == 0){
            return 0;
        }
        int more = Math.max(m.length, m[0].length);
        int less = Math.min(m.length, m[0].length);
        boolean rowMore = more == m.length;
        if (!rowMore) {
            int temp = more;
            more = less;
            less = temp;
        }
        int[] dp = new int[less--];
        dp[less] = Math.max(1, 1 - (rowMore ? m[--more][less] : m[less][--more]));
        for (int i = less - 1; i >= 0; i--) {
            dp[i] = Math.max(dp[i + 1] - (rowMore ? m[more][less] : m[less][more]), 1);
        }
        int right = 0;
        for (int i = more - 1; i >= 0; i--) {
            dp[less] = Math.max(1, dp[less] - (rowMore ? m[i][less] : m[less][i]));
            right = dp[less];
            for (int j = less - 1; j >= 0; j--) {
                dp[j] = Math.max(Math.min(dp[j] - (rowMore ? m[i][j] : m[j][i]),
                        right - (rowMore ? m[i][j] : m[j][i])), 1);
                right = dp[j];
            }
        }
        return dp[0];
    }

}
